Recently, in the field of user authentication systems, a user authentication system based on a so-called matrix authentication scheme has been developed as one type of challenge/response scheme (see, for example, the following Patent Document 1). In the matrix authentication, a matrix-like presentation pattern having random numbers arranged in a given pattern format is presented to a user who intends to be authenticated, and a one-time-password derivation rule is used as a password of the user and applied to certain ones of a plurality of pattern elements (the respective random numbers) comprised in the presentation pattern, to create a one-time password. Further, the same presentation pattern is shared between a server and a client, and the one-time password created as a result of applying the one-time-password derivation rule serving as the user's password to the presentation pattern in the client is compared with a verification code created as a result of applying the one-time-password derivation rule serving as the user's password to the presentation pattern in the server. In this manner, user authentication is performed without directly comparing between the passwords. In the matrix authentication, a one-time-password derivation rule serving as a password consists of positions of two or more elements to be selected on a matrix, and an order of the selection, and has a feature that a user can easily remember it as an image, and it cannot be figured out even if a one-time password is subjected to a furtive glance during an operation of entering the one-time password.
An off-line user authentication system has also been developed which is designed to allow a matrix authentication even when a client is not connected to a server via a network, i.e., in an off-line state (see the following Patent Document 2). An off-line authentication system employing a matrix authentication is designed to store, in an off-line authentication client, a plurality of pattern element sequences each constituting a presentation pattern, and a plurality of verification codes each created by applying a one-time-password derivation rule to a respective one of the presentation patterns and then subjecting the obtained result to a one-way function operation using a hash function, and perform authentication in such a manner that one of the stored pattern element sequences is selected to generate a presentation pattern, and a code created by subjecting an entered one-time password to the one-way function operation is compared with a corresponding one of the verification codes. Thus, the off-line authentication client can display or present a presentation pattern by itself. In addition, the verification codes for verifying passwords are stored in a hashed form, without storing passwords themselves. This makes it possible to achieve an off-line matrix authentication having high security capable of preventing password leakage even if a client is analyzed.
FIG. 21 is a functional block diagram of an off-line user authentication system 2100 designed to allow a conventional matrix authentication. In this system, a user ID 2181 is entered by a user of a client 2151 through a user-ID input unit 2152, and transmitted to an authentication support server 2101 through a verification-data requestor 2153. In the authentication support server 2101, the entered user ID 2181 is received through a verification-data-request receiver 2103. Then, a pattern generator 2104 is operable to generate a plurality of pattern element sequences 2190 which are information for creating respective ones of a plurality of presentation patterns 2210 (FIG. 22) corresponding to the entered user ID, and a verification-code creator 2106 is operable to create a plurality of verification codes 2193 which correspond to respective ones of the presentation patterns and a one-time-password derivation rule 2102b corresponding to a user ID 2102a stored in a password storage 2102. The pattern element sequences 2190 and the verification codes 2193 are preliminarily transmitted to the client 2151 through a patter transmitter 2105 and a verification-code transmitter 2111, respectively. In the client 2151, the pattern element sequences 2190 and the verification codes 2193 are received through a pattern receiver 2154 and a verification-code receiver 2162, respectively, and stored in verification-data storage 2161. Then, a pattern selector 2163 is operable, in response to an entry of the user ID by the user through the user-ID input unit 2153, to select one of the pattern element sequences 2190 stored in the verification-data storage 2161. A pattern display unit 2155 is operable, based on the selected pattern element sequence 2190, to display a presentation pattern 2210 in the client 2151, and a one-time-password input unit 2156 is operable to accept an entry of a cone-time password from the user. A verification-code determiner 2164 is operable to determine one of the verification codes 2193 which corresponds to the user ID and the selected pattern element sequence and read the determined verification code 2193 from the verification-data storage 2161, and a user authentication unit 2165 is operable to compare a code created by subjecting the entered one-time password to a one-way function operation with the verification code 2193 to perform a user verification.
FIG. 22 is a conceptual diagram showing a process of creating a presentation pattern 2210 in a conventional matrix authentication system. FIG. 22 illustrates a pattern element sequence 2190 comprising a plurality of pattern elements which are one-digit numerals of 0 to 9, and a presentation pattern 2210, wherein the pattern elements comprised in the pattern element sequence are arranged at respective positions in a pattern format consisting of four 4×4 matrixes. In this example, the authentication support server 2101 is operable to generate sixty four one-digit numerals as the pattern elements to be comprised in the presentation pattern 2210, by a random-number generation algorithm, and then transmit a pattern element sequence 2190 created by sequencing the generated numerals, to the client 2151. The client 2151 is operable to, after receiving the pattern element sequence 2190 from the authentication support server 2101, sequentially arrange the pattern elements comprised therein, at respective positions in a given pattern format (in this example, four 4×4 matrixes), so as to create the presentation pattern 2210, and display the created presentation pattern 2210 on a display screen.
FIG. 23 is a conceptual diagram showing a process of entering a one-time password in the matrix authentication scheme. The user sequentially extracts certain ones of the numerals displayed at given positions on the matrix, by applying the one-time-password derivation rule to the presentation pattern 2210, and enters the extracted numerals from the one-time-password input unit 2156. The arrows and circles indicated by broken lines in FIG. 23 denote that the one-time password based on the presentation pattern 2210 is entered from a keyboard 2300.